package com.lwl.shua.class01;

/**
 * @author lwl
 * @Description * 给定两个数组x和hp，长度都是N。
 * * x数组一定是有序的，x[i]表示i号怪兽在x轴上的位置
 * * hp数组不要求有序，hp[i]表示i号怪兽的血量
 * * 为了方便起见，可以认为x数组和hp数组中没有负数。
 * * 再给定一个正数range，表示如果法师释放技能的范围长度(直径！)
 * * 被打到的每只怪兽损失1点血量。
 * * 返回要把所有怪兽血量清空，至少需要释放多少次aoe技能？
 * * 三个参数：int[] x, int[] hp, int range
 * * 返回：int 次数
 * @date 2025/9/6 11:04
 */
public class Code06AOE {

    public static int minAoe1(int[] x, int[] hp, int range) {
        // 每个位置到技能可以达到的最右侧
        int[] cover = new int[x.length];
        int r = 0;
        for (int i = 0; i < x.length; i++) {
            while (r < x.length && x[r] - x[i] <= range) {
                r++;
            }
            cover[i] = r;
        }
        int ans = 0;
        for (int i = 0; i < x.length; i++) {
            // 最左侧还没死掉的怪，干掉它需要多少伤害
            int needPower = hp[i];
            if (needPower <= 0) {
                continue;
            }
            for (int j = i; j < cover[i]; j++) {
                hp[j] -= needPower;
            }
            ans += needPower;
        }
        return ans;
    }

}
